{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Erasure Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumUniqueSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除子数组的最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>nums</code> ，请你从中删除一个含有 <strong>若干不同元素</strong> 的子数组<strong>。</strong>删除子数组的 <strong>得分</strong> 就是子数组各元素之 <strong>和</strong> 。</p>\n",
    "\n",
    "<p>返回 <strong>只删除一个</strong> 子数组可获得的 <strong>最大得分</strong><em> 。</em></p>\n",
    "\n",
    "<p>如果数组 <code>b</code> 是数组 <code>a</code> 的一个连续子序列，即如果它等于 <code>a[l],a[l+1],...,a[r]</code> ，那么它就是 <code>a</code> 的一个子数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,2,4,5,6]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>最优子数组是 [2,4,5,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,2,1,2,5,2,1,2,5]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>最优子数组是 [5,2,1] 或 [1,2,5]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-erasure-value](https://leetcode.cn/problems/maximum-erasure-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-erasure-value](https://leetcode.cn/problems/maximum-erasure-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,4,5,6]', '[5,2,1,2,5,2,1,2,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        l,r = 0,0\n",
    "        visited = [False] * 10001\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        while r<len(nums):\n",
    "            while visited[nums[r]]:\n",
    "                cur -= nums[l]\n",
    "                visited[nums[l]] = False\n",
    "                l += 1\n",
    "            cur += nums[r]\n",
    "            visited[nums[r]] = True\n",
    "            res = max(res,cur)\n",
    "            r+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        sum_s = 0\n",
    "        while len(nums) != 0:\n",
    "            if nums[-1] not in stack:\n",
    "                stack.append(nums.pop())\n",
    "                sum_s += stack[-1]\n",
    "                res = max(res, sum_s)\n",
    "            else:\n",
    "                sum_s -= stack[0]\n",
    "                del stack[0]         \n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        if len(set(nums)) == len(nums):\n",
    "            return sum(nums)\n",
    "        \n",
    "        left, right = 0, 1\n",
    "        curSet = set([nums[0]])\n",
    "        maxScore, curScore = nums[0], nums[0]\n",
    "        while right < len(nums):\n",
    "            if nums[right] not in curSet:\n",
    "                curSet.add(nums[right])\n",
    "                # curScore += nums[right]\n",
    "            else:\n",
    "                while nums[left] != nums[right]:\n",
    "                    # print(curSet, '------', nums[left], nums[right], left, right, '1111111')\n",
    "                    curSet.remove(nums[left])\n",
    "                    left += 1\n",
    "                    # print(curSet, nums[left], nums[right], left, right, '2222222')\n",
    "                    \n",
    "                left += 1\n",
    "            right += 1\n",
    "                # curScore = sum(nums[left:right+1])\n",
    "            \n",
    "            # print(curSet, 'zzzz')\n",
    "            maxScore = max(maxScore, sum(curSet))\n",
    "        \n",
    "        return maxScore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==0:return 0\n",
    "        if n==1:return nums[0]\n",
    "        s,left = 0,0\n",
    "        sets =set()\n",
    "        max_val = 0  \n",
    "        for right in range(0,n):\n",
    "            if nums[right] in sets:\n",
    "                while nums[right]!=nums[left]:\n",
    "                    s -= nums[left]\n",
    "                    sets.remove(nums[left])\n",
    "                    left+=1\n",
    "                left+=1\n",
    "            else:\n",
    "                s +=nums[right]\n",
    "                sets.add(nums[right])\n",
    "            max_val = max(max_val,s)\n",
    "            print(right,s )\n",
    "        return max_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.append(0)\n",
    "        dic = {}\n",
    "        p,ret = -1 , 0\n",
    "        for i in range(n):\n",
    "            p = max(p,dic.get(nums[i],-1))\n",
    "            dic[nums[i]]  = i \n",
    "            nums[i] += nums[i-1]\n",
    "            ret = max(nums[i] - nums[p],ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        # 含有 若干不同元素 的子数组 的和\n",
    "        # 滑动窗口\n",
    "\n",
    "        left,res = 0,0\n",
    "        cnt = defaultdict(int) # 标配用来记录当前每个数字出现的次数\n",
    "        sum_ = 0\n",
    "        for right,num in enumerate(nums):\n",
    "            cnt[num]+=1 # 二话不说，直接哈希表统计\n",
    "            sum_ += num # 题目得分是和的概念，所以来一个sum_统计一下和\n",
    "            if cnt[num]==1: #满足条件（加入新对象后，也没有重复的。注意，这里是配合后面使用的，因为后续的while,剔除了重复的部分）\n",
    "                res = max(res,sum_)\n",
    "            while cnt[num]>1: # 如果出现重复，开始移动窗口\n",
    "                cnt[nums[left]]-=1\n",
    "                sum_ -= nums[left]\n",
    "                # if cnt[nums[left]]==0:\n",
    "                #     del cnt[nums[left]]\n",
    "                left+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        sum_ = 0\n",
    "        max_ = 0\n",
    "        hash = {}\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            sum_ += nums[end]\n",
    "            hash[nums[end]] = hash.get(nums[end], 0) + 1\n",
    "            if len(hash) == end - start + 1:\n",
    "                max_ = max(sum_, max_)\n",
    "            while len(hash) < end - start + 1:\n",
    "                head = nums[start]\n",
    "                hash[head] -= 1\n",
    "                if hash[head] == 0:\n",
    "                    del hash[head]\n",
    "                sum_ -= nums[start]\n",
    "                start += 1\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "\n",
    "        lst = set()\n",
    "        n = len(nums)\n",
    "        l = r = ans = cnt = 0\n",
    "        while r < n:\n",
    "            while l < r and nums[r] in lst:\n",
    "                cnt -= nums[l]\n",
    "                lst.remove(nums[l])\n",
    "                l += 1\n",
    "            lst.add(nums[r])\n",
    "            cnt += nums[r]\n",
    "            ans = max(ans, cnt)\n",
    "            r += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        cnt=Counter()\n",
    "        ans=left=sum_=0\n",
    "\n",
    "        for right,val in enumerate(nums):\n",
    "            cnt[val]+=1\n",
    "            sum_+=val\n",
    "            \n",
    "\n",
    "\n",
    "            while cnt[val] > 1:\n",
    "                cnt[nums[left]]-=1\n",
    "                sum_-=nums[left]\n",
    "                if cnt[nums[left]]==0:\n",
    "                    cnt.pop(nums[left])\n",
    "                left+=1\n",
    "            ans=max(ans,sum_)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        data structure: 序列，列表\n",
    "        algorithm:\n",
    "            不定长度滑动窗口\n",
    "            滑动方式\n",
    "                j+=1，i当不满足题目条件时候移动至满足条件为止\n",
    "        speical:\n",
    "\n",
    "        \"\"\"\n",
    "        #数字计数表\n",
    "        digit_set=set()\n",
    "        max_sum = 0\n",
    "        interval_sum = 0\n",
    "        i = 0\n",
    "        for j, num in enumerate(nums):\n",
    "            if num in digit_set:#目前窗口发现重复数字,计数并滑动\n",
    "                #发现重复元素后计数\n",
    "                max_sum = max(interval_sum ,max_sum)\n",
    "                while num in digit_set:#移动到无与当前值重复的元素,即左边界收缩到满足题目条件后再移动\n",
    "                    digit_set.remove(nums[i])\n",
    "                    interval_sum -= nums[i]\n",
    "                    i += 1\n",
    "            elif  j ==len(nums) - 1:#最后一个元素不是重复元素,仍需要一次额外的累加和计数\n",
    "                interval_sum  += num\n",
    "                max_sum = max(interval_sum ,max_sum)\n",
    "            #先进行判断，最后再累加和添加进set\n",
    "            interval_sum  += num\n",
    "            digit_set.add(num) \n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        max=0\n",
    "        dic={}\n",
    "        begin=0\n",
    "        sum=0\n",
    "        for i in range(len(nums)):\n",
    "            sum+=nums[i]\n",
    "            dic[nums[i]]=dic.get(nums[i],0)+1\n",
    "            while dic[nums[i]]>1:\n",
    "                dic[nums[begin]]-=1\n",
    "                sum-=nums[begin]\n",
    "                begin+=1\n",
    "            if sum>max:\n",
    "                max=sum\n",
    "        return max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        cnt = Counter()\n",
    "        left = 0\n",
    "        sum_ = 0\n",
    "        \n",
    "        for right, x in enumerate(nums):\n",
    "            #print(left,right,cnt,ans,x)\n",
    "            while cnt[x] == 1:\n",
    "                sum_ -= nums[left]\n",
    "                cnt[nums[left]] -= 1\n",
    "                left += 1\n",
    "\n",
    "            cnt[x] += 1\n",
    "            sum_ += x\n",
    "            ans = max(ans, sum_)\n",
    "            #print(left,right,ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        first =  [-1]*(max(nums)+1)\n",
    "        count = 0\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            count += nums[i]\n",
    "            if first[nums[i]]!=-1:\n",
    "                while l<=first[nums[i]]:\n",
    "                    count -= nums[l]\n",
    "                    first [nums[l]] =-1\n",
    "                    l+=1\n",
    "            first[nums[i ]] = i\n",
    "            if count > ans :\n",
    "                ans =count\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUniqueSubarray(self, nums: List[int]) -> int:\n",
    "        sum_, max_sum, hasmap = 0, 0, {}\n",
    "\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            tail = nums[end]\n",
    "            sum_ += tail\n",
    "            hasmap[tail] = hasmap.get(tail, 0) + 1\n",
    "            if end - start + 1 == len(hasmap):\n",
    "                max_sum = max(max_sum, sum_)\n",
    "\n",
    "            while end - start + 1 > len(hasmap):\n",
    "                head = nums[start]\n",
    "                hasmap[head] -= 1\n",
    "                if hasmap[head] == 0:\n",
    "                    del hasmap[head]\n",
    "                sum_ -= nums[start]\n",
    "                start += 1\n",
    "        return max_sum"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
